package top.hkyzf.study.leetcode.tree;

import org.junit.Test;

/**
 * @author 朱峰
 * @date 2022-1-26 11:06
 */
public class 填充每个节点的下一个右侧节点指针_116 {
    public TreeNode connect(TreeNode root) {
        if (root != null) {
            connectTwoNode(root.left, root.right);
        }
        return root;
    }

    private void connectTwoNode(TreeNode node1, TreeNode node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        // 连接
        node1.next = node2;
        // 连接子树
        connectTwoNode(node1.left, node1.right);
        connectTwoNode(node2.left, node2.right);
        // 连接两个子树之间
        connectTwoNode(node1.right, node2.left);
    }

    @Test
    public void testConnect () {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        TreeNode connect = connect(root);
        connect.printNext();
    }
}
